群论笔记 05

what if the 'a' and 'b' are same set? what if 'a' and 'b' have intersection? 1. the union of a set with itself, is this set itself 2. I can tag the repeated elements, and say that, although they are same elemetns, but with different tags, this is from 'a', another is from 'b'. this is called discriminated union: https://www.wikiwand.com/en/Tagged\_union

we can make c as a disjoint union, and c' as a ordinary union, but we can not reverse this, you CANNOT make c as a union and c' as a disjoint union.

why?

ONE element in c will map to TWO elements in c', this is NOT allowed as a function.

this is point view of Set Theory, when your union 2 sets who have duplicated elements, and these elements will keep in union result with different tags.

data Either a b = Left a | Right b

val x: Either[Int, String] = Right("good")

These constructor directly correspond to injections, like all "may or" types in scala: * Either: may this or that * Option: may value or None * Try: may value or Exception * Future: may value(avaiable at sometime) or Exception

many collection type in scala is product-type: * Tuple: (Int, Boolean)

we have a multiplication ,the product is similar to multiplicaiton, what does it mean that such a multiplication? It means we have a monoid, at least. Monoid is something associative, something multiplication, something unit. But, what we want to talk about is types, algebraic data types. Is product in the algebraic datatype has same way as monoid.

remeber monoid? 1. Integer form a monoid under production, with unity 1; 2. Integer form a monoid under addition, with unity 0; 3. String form a monoid under concatenation, with unity empty string 4. List form a monoid, under append, with unity empty list. tips ： this is why in Haskell string is list, because they are both monoid.

you can see that, all the operator who makes a set a monoid is something like a multiplication, a combination, not a union.

so we can say a monoid have 3 attributes: 1. unit in set 2. associative on operator 3. combination on view

just show trait of isomorphism)

:CUSTOM_ID: symmetric-up-to-isomorphism-vs.symmetricnot-related-to-monoid-just-show-trait-of-isomorphism

product produce some pairs: (a,b) = (b,a) . This 2 pairs are not same, but they have same information, the only difference is just the way of encoding — Not Same, but isomorphic. We can define a function like "swap", which is a isomorphism between (a,b) and (b,a), in other words: They are not same, but same up to isomorphism.

// (a,b)!=(b,a)
swap:: (a,b)->(b,a)
swap p = (snd p, fst p)
swap_reverse q = (snd q, fst q)

it's obvious that swap is a isomorphism between (a,b) and (b,a), so we can say (a,b) and (b,a) is isomorphic

If the production as an binary operator which under which build up a monoid, must statisfy associative rule: ((a,b),c) = (a,(b,c)). no, it's not satisfied. But they have the same information, but rearrange them, similarly we can find a function like "assoc", which is isomorphism between ((a,b),c) and (a,(b,c)), in other words: The production is not associative, but associative up to isomorphism.

// ((a,b),c) != (a,(b,c))
assoc :: ((a,b),c) -> (a,(b,c))
assoc p = <some pattern match clause>
assoc_reverse q = <some pattern match clause>

vs. monid-associative for Integer under multiplication: 3/(4/5) = (3/4)/5

• production: an similar-associativity on type*(*set)
• monoid: an true-associativity on element

the same thing can apply to the unit: production dose not satisfy (a,()) = a, but they have the same information. we also can find a function like "munit", which is a isomorphism between (a,()) and a.

// (a,()) != a
munit :: (a,()) -> a
munit p = fst p
munit_reverse q = (q,())

vs. monid-unit for Integer under multiplication: 3*1 = 3

• production: an similar-unit on type*(*set)
• monoid: an true-unit on element

remeber monoid? 1. Integer form a monoid under production, with unity 1; 2. Integer form a monoid under addition, with unity 0; 3. String form a monoid under concatenation, with unity empty string 4. List form a monoid, under append, with unity empty list. tips ： this is why in Haskell string is list, because they are both monoid.

So you can find that, monoid is just a special set (for unit), with some *special operator on set*(for binary operator).

what about the product?

It's something related to many types( or we can say many sets)

What is this structure called, both multiplication and addition in the same thing — ring

A really Ring has some other things, like inversement of addition, inversement of multiplication.

If a Ring don't have all these inverse elements, it's called semiring or rig*(no spell mistake) = *Ring without negative.

sleight of hand

data List a = Nil | cons a (List a) It is so self-explanatory , and give a recursive definition of List > - "what is a List" > - "it's empty or concate a value with a List"

data List a = Nil | cons a (List a)

In algebraic datatypes, we can find the algebraic equation:

l(a) = 1 + a * l(a)
     = 1 + a * (1 + a * l(a))
     = ...
     = 1 + a + a*a + a*a*a + ...

then, what is this 1+a+a^2+a^3+..., this is just what we say in haskell

List(Nothing) | List a | List a a | List a a a | List a ... | List a_infinite 

which means *all kinds of List*(has 0~infinite elements) who has the type of element a

data List a = Nil | Cons a (List a)